package main.Q701_800;

import java.util.Deque;
import java.util.LinkedList;

public class Q731_740 {
    public static void main(String[] args) {
        System.out.println("Question731：我的日程安排表Ⅱ");
        System.out.println("Question732：");
        System.out.println("Question733：图像渲染");
        System.out.println("Question734：");
        System.out.println("Question735：行星碰撞");
        System.out.println("Question736：");
        System.out.println("Question737：");
        System.out.println("Question738：");
        System.out.println("Question739：每日温度");
        System.out.println("Question740：删除并获得点数");
    }
}

class Question731{

}

class Question733{
    int newColor=0;
    int intiColor=0;
    public void process(int[][] image,int[][] result,int row,int col){
        int r= image.length,c=image[0].length;
        result[row][col]=newColor;
        if (row-1>=0&&image[row-1][col]==intiColor&&result[row-1][col]!=newColor) process(image,result,row-1,col);//上
        if (row+1<r&&image[row+1][col]==intiColor&&result[row+1][col]!=newColor) process(image,result,row+1,col);//下
        if (col-1>=0&&image[row][col-1]==intiColor&&result[row][col-1]!=newColor) process(image,result,row,col-1);//左
        if (col+1<c&&image[row][col+1]==intiColor&&result[row][col+1]!=newColor) process(image,result,row,col+1);//右
    }
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int row= image.length,col=image[0].length;
        int[][] result=new int[row][col];
        for (int i=0;i<row;i++){
            for (int j=0;j<col;j++)
                result[i][j]=image[i][j];
        }
        intiColor=image[sr][sc];
        newColor=color;
        process(image,result,sr,sc);
        return result;
    }
}

class Question735{
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> deque=new LinkedList<>();
        int i=asteroids.length-1;
        while (i>=0){
            if (deque.isEmpty()||deque.peekFirst()>0){//队首为空或为正数
                deque.addFirst(asteroids[i]);
            }else {//队首为负数
                int temp=deque.peekFirst();
                if (asteroids[i]<0){//新入队元素为负数
                    deque.addFirst(asteroids[i]);
                }else {//新入队元素为正数
                    if (temp+asteroids[i]==0){//大小相同
                        deque.pollFirst();
                    }else {//大小不同
                        while (temp<0&&temp+asteroids[i]>0){
                            deque.pollFirst();
                            if (!deque.isEmpty()) temp=deque.peekFirst();
                            else break;
                        }
                        if ((temp>0&&temp+asteroids[i]!=0)||deque.isEmpty()) deque.addFirst(asteroids[i]);
                        else if (temp+asteroids[i]==0) deque.pollFirst();
                    }
                }
            }
            i--;
        }
        int[] result=new int[deque.size()];
        for (int j=0;j< result.length;j++){
            result[j]=deque.pollFirst();
        }
        return result;
    }
}

class Question739{
    public int[] dailyTemperatures(int[] temperatures) {
        int length= temperatures.length;
        int[] result=new int[length];
        Deque<Integer> deque=new LinkedList<>();
        deque.addLast(0);
        for (int i=1;i<length;i++){
            while (!deque.isEmpty()&&temperatures[i]>temperatures[deque.peekLast()]){//当前温度大于队尾温度
                int temp=deque.pollLast();
                result[temp]=i-temp;
            }
            deque.addLast(i);
        }
        while (!deque.isEmpty()){
            result[deque.pollLast()]=0;
        }
        return result;
    }
}

class Question740{
//    public static int process(int sum,List<Integer> lastList){
//        if (lastList.size()==0) return sum;
//        int size=lastList.size();
//        int curSum=0;
//        for (int i=0;i<size;i++){
//            List<Integer> tempList=new ArrayList<>();
//            tempList.addAll(lastList);
//            Integer deleteNum=tempList.get(i),NumS=deleteNum-1,NumB=deleteNum+1;
//            tempList.remove(deleteNum);
//            while (tempList.contains(deleteNum-1)) tempList.remove(NumS);
//            while (tempList.contains(deleteNum+1)) tempList.remove(NumB);
//            int tempSum=process(deleteNum,tempList);
//            curSum= Math.max(curSum,tempSum);
//        }
//        return sum+curSum;
//    }
    public int process(int[] nums){
        int pre=nums[0],cur=Math.max(nums[0],nums[1]);
        for (int i=2;i< nums.length;i++){
            int temp=cur;
            cur=Math.max(pre+nums[i],cur);
            pre=temp;
        }
        return cur;
    }
    public int deleteAndEarn(int[] nums) {
        int max=Integer.MIN_VALUE;
        for (int num:nums) max=Math.max(max,num);//记录最大值为多少
        int[] arr=new int[max+1];
        for (int num:nums) arr[num]+=num;//记录每个数字在数组内的总和
        int maxSum=process(arr);
        return maxSum;
    }
}